#include<stdio.h>
#include<stdlib.h>
#define ElementType int

struct Node
{
    ElementType data;
    struct Node *left;
    struct Node *right;
};

struct Node *RotateRight(struct Node *node)
{
    struct Node *t=node->left;
    node->left=t->right;
    t->right=node;
    return t;
}

struct Node *RotateLeft(struct Node *node)
{
    struct Node *t=node->right;
    node->right=t->left;
    t->left=node;
    return t;
}

struct Node *RotateLeftRight(struct Node *node)
{
    node->left=RotateLeft(node->left);
    return RotateRight(node);
}

struct Node *RotateRightLeft(struct Node *node)
{
    node->right=RotateRight(node->right);
    return RotateLeft(node);
}

int GetTreeHeight(struct Node *node)
{
    if(node==NULL)
        return 0;

    int leftHeight=GetTreeHeight(node->left);
    int rightHeight=GetTreeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight:rightHeight)+1; 
}

struct Node *InsertData(struct Node *node,ElementType data)
{
    struct Node *newNode=(struct Node *)malloc(sizeof(struct Node));
    if(newNode==NULL)
    {
        printf("newNode malloc error!\n");
        return NULL;
    }
    newNode->data=data;
    newNode->left=newNode->right=NULL;

    if(node==NULL)
    {
        node=newNode;
    }
    else if(data < node->data)
    {
        node->left=InsertData(node->left,data);
        if(GetTreeHeight(node->left)-GetTreeHeight(node->right)>1)
        {
            if(data<node->left->data)
            {
                node=RotateRight(node);
            }
            else
            {
                node=RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right=InsertData(node->right,data);
        if(GetTreeHeight(node->left)-GetTreeHeight(node->right)<-1)
        {
            if(data<node->right->data)
            {
                node=RotateRightLeft(node);
            }
            else
            {
                node=RotateLeft(node);
            }
        }
    }
    return node;
}

void MidPrint(struct Node *node)
{
    if(node!=NULL)
    {
        MidPrint(node->left);
        printf("%d ",node->data);
        MidPrint(node->right);
    }
}

void PrevPrint(struct Node *node)
{
    if(node!=NULL)
    {
        printf("%d ",node->data);
        PrevPrint(node->left);       
        PrevPrint(node->right);
    }
}

void PostPrint(struct Node *node)
{
    if(node!=NULL)
    {        
        PostPrint(node->left);       
        PostPrint(node->right);
        printf("%d ",node->data);
    }
}

int main()
{
    struct Node *root=NULL;
    int a[]={1,2,3,4,5,6,7,8,9,10};
    for(int i=0;i<10;i++)
    {
        root=InsertData(root,a[i]);
    }
    MidPrint(root);
    printf("\n");
    PrevPrint(root);
    printf("\n");
    
    printf("root:%d\n",root->data);
    return 0;
}